# [seqfan] Re: number of different digit patterns of n-digit numbers

Alois Heinz heinz at hs-heilbronn.de
Fri Aug 28 12:47:22 CEST 2009

```I can send in the two sequences for 9 parts and 10 parts.

The terms I calculated differ from the output of the PARI program.

But I used a second method to check the terms, see reference from A099263:
N. Moreira and R. Reis, On the Density of Languages Representing Finite Set
Partitions, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.8.
http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Moreira/moreira8.pdf

# 1st method
with (combinat): a:= n-> add (stirling2 (n, k), k=1..10): seq (a(n),
n=1..30);

# 2nd method
g:=proc(c,k) option remember;
if c=1 and k=1 then 1
elif c>1 and k=1 then g(c-1,1) + (-1)^(c-1)/(c-1)!
else g(c-1,k-1)/k
fi
end;
g10:= n-> add (g(10,k)*k^n, k=1..10);
seq (g10(n), n=1..30);

# equal to
a:= n-> (1334960 +667485*2^n +222480*3^n +55650*4^n +11088*5^n
+1890*6^n +240*7^n +45*8^n +10^n)/10!: seq (a(n), n=1..30);

# all give

1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678569, 4213530, 27641927,
190829797, 1381367941, 10448276360, 82285618467, 672294831619,
5676711562593,
49344452550230, 439841775811967, 4005444732928641, 37136385907400125,
349459367068932740, 3328651061864065627, 32019561236874324063,
310458637501567882137, 3029333888602793961490, 29708969836672895454647,
292533334396074979037085

Alois

franktaw at netscape.net schrieb:
> Yes, it is the sum of the first k Stirling numbers of the second kind.
>
> I didn't use that for the PARI program since PARI (at least the version
> I currently have) doesn't have a primitive for Stirling numbers.
>
> Franklin T. Adams-Watters
>
>
> -----Original Message-----
> From: David Wilson <davidwwilson at comcast.net>
>
> Would this sequence have a formula in terms of Stirling number of the
> second
> kind?
>
> ----- Original Message -----
> From: <franktaw at netscape.net>
> To: <seqfan at list.seqfan.eu>
> Sent: Thursday, August 27, 2009 6:44 PM
> Subject: [seqfan] Re: number of different digit patterns of n-digit
> numbers
>
>
>> This is just the number of set partitions of n into at most 10 parts.
>> The condition that the first ball not go in the first box is not
>> relevant; you can always permute the digits so that the first one is
>> not zero.
>>
>> Sequences of this type are in the OEIS for up to 8 (i.e., set
>> partitions into at most 8 parts, which is A099263).
>>
>> Here's a PARI program to generate sequences of this type:
>>
>>
> a(n,k)=local(ps);ps=exp(sum(i=1,k,x^i/i!)+x*O(x^n));vector(n,i,polcoeff(p
>
>> s,i)*i!)
>>
>> Here n is the number of terms you want, and k is the maximum number of
>> parts.  For k = 10, we get:
>>
>> 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678569, 4213584,
>> 27644267, 190897305, 1382935569, 10479884654, 82861996310,
>> 682044632178, 5832378929502, 51720008131148, 474821737584174,
>> 4506150050048604, 44145239041717738, 445876518513670356,
>> 4637570299337888742, 49618383871367215282, 545551902886241817684,
>> 6158380541703927984540, 71311068810038965177080,
>> 846359710104516310431744
>>
>> Franklin T. Adams-Watters
>>
>> -----Original Message-----
>> From: Tanya Khovanova <mathoflove-seqfan at yahoo.com>
>>
>> Dear Sequence Fans,
>>
>> I would like to propose a new sequence:
>>
>> Number of different digit patterns of n-digit numbers.
>> or
>> Number of ways to put n labeled balls into 10 indistinguishable boxes
>> so that
>> the first ball can't go into the first box.
>> or
>> Number of equivalence classes of n-digit numbers with respect to digit
>> permutations.
>>
>> The sequence starts at Bell numbers: 1,2,5,15,52,203,877,4140,21147,
>> but are not
>> Bell numbers.
>>
>> I know that OEIS is on vacation, but I need this sequence for my blog
>> essay. So
>> I am not sure if I should submit.
>>
>> Besides, I need more terms to distinguish it from Bell numbers.
>>
>> What should I do, and can you help?
>>
>> Tanya

```