For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

1
vote
3answers
57 views

Number of ways to write $n$ as sum of $k$ non-negative integers without 1

During my calculations I ended up at the following combinatorial problem: In how many way can we write the integer $n$ as the sum of $k$ non-negative integers, each different to one, i.e. calculate ...
3
votes
0answers
23 views

Iterate Over Integer Partition Refinement in Sage

A partition of an integer $n$ is a non-decreasing list of positive integers summing to $n$. For example, $3$ can be partitioned as $1 + 1 + 1$, $1 + 2$ or just $3$, but $2 + 1$ is indistinct from $1 + ...
1
vote
1answer
33 views

expect number of multipe draws

There are 100 numbered balls in an urn. We make 100 random draws with replacement. Of course, we can not expect to draw every number exactly once, there will be multiples. What is the expected value ...
3
votes
1answer
39 views

Count integer squares coordinates

Let $n$ be given an natural number. We want to find the number of squares which have corners with integer coordinates between $0$ and $n$. For example $n=1$, there is only one square; $n=2$ there are ...
0
votes
1answer
44 views

How many diagonals does a decagon have?

How many diagonals does a decagon have? I have just learnt permutations, dispositions, combinations. How can I solve it with these concepts? I drew it and it was $35$ diagonals. How can I prove ...
4
votes
1answer
65 views

Count how many “free words” of a certain length reduce to the identity

Let $F_n$ be the free group with $n$ generators $g_1,\ldots,g_n$. I'm trying to settle the following: Question. For a fixed even integer $m$, is there a systematic way to count how many words ...
0
votes
0answers
9 views

incremental knapsack

Is there a way to compute the knapsack problem incrementally? Any approximation algorithm? I am trying to solve the problem in the following scenario. Let D be my data set which is not ordered and ...
0
votes
1answer
26 views

Problem on Inclusion & Exclusion Principle

Book has the following & solution to it too, pls clear my confusion: On rainy day , five gentlemen A, B, C,D, E attend a party after leaving their umbrellas in a checkroom. After the party is ...
0
votes
0answers
17 views

Evaluation sum indexed by non decreasing sequences

During solving a problem from probability theory, I've met the following sum to evaluate: $$p_n(N) = \frac{1}{N!}\sum_{0\leqslant k_1\leqslant\ldots\leqslant k_n\leqslant N}\frac{k_1\cdot\ldots\cdot ...
4
votes
0answers
27 views

Find most varied match assignments for a 4-player card game

I'm a programmer and confronted with a particularly hard (at least for me) problem I couldn't find an answer for. This is not a school task or anything. It is something I need personally. I've ...
-3
votes
0answers
37 views

Connectivety of the Erdős–Rényi random graph [closed]

Let G be a graph in G(n, p) (Erdős–Rényi model) I want to prove that that P( G(n, p) where p ≥ ( lnn/10n) and number of tree components on 11 vertices = 0 ) converges to 1 and lnn/n is a ...
2
votes
2answers
2k views

Lexicographical rank of a string with duplicate characters

Given a string, you can find the lexicographic rank of the string using this algorithm: Let the given string be “STRING”. In the input string, ‘S’ is the first character. There are total 6 ...
4
votes
1answer
39 views

How many 4 digit pins on set {0-9}

A password can be any 4 digit {0...9}. 1.)How many possible passwords are there? for this I did $10^4 = 10,000$ 2.) How many possible passwords with no repeated digits? $10*9*8*7 = 5040$ 3.) How ...
3
votes
1answer
39 views

Find a generating function for $a_r=(r-1)^2$

Problem Find a generating function for $a_r=(r-1)^2$ My Solution $$g(x)=1+x+x^2+x^3+\cdots=\frac{1}{1-x}$$ $$g'(x)=1+2x+3x^2+4x^3+\cdots=\frac{1}{(1-x)^2}$$ $$x\times ...
0
votes
2answers
29 views

4-Sequences {0…9}

My questions are given the set {0,1,2,3,4,5,6,7,8,9}, 1) How many 4-sequences are there? (would this be $10*10 * 10 * 10 = 10,000)? $ since the max possible numbers given to each 4 slots is 10. 2) ...
1
vote
1answer
27 views

5 letter password either lowercase or uppercase

Given that you can have 5 letter password that contains either lowercase or uppercase. My questions are: 1) How many possible passwords are there? I did $52^5 = 380,204,032$ since there are 52 ...
0
votes
0answers
22 views

Combination and Permutation How many words can be formed? [duplicate]

A contest consists of finding all code words that can be formed from the letters in the word "alpha".Assume that the letter "a" can be used twice but the others at most once: a)How many five-letter ...
1
vote
1answer
26 views

Chromatic number of Erdos-Renyi random graphs $G(n,m)$

In Erdos-Renyi random graphs $G(n,m)$, set $n=4$ and $m=5$. The question is as follows: What is the probability for to having Chromatic number exactly 2 in the case of $G(4,5)$; in other words what ...
5
votes
3answers
6k views

Number of equivalence relations on a finite set

I need a hint for computing the number of ways in which all the equivalent classes on a set of $n$ elements can be realized. For example, if the set has 2 elements ${a,b}$, then there are 2 possible ...
1
vote
0answers
28 views

Find an ordinary generating function whose $a_r = 3r + 7$

Problem Find an ordinary generating function whose coefficient $a_r = 3r + 7$. My Solution $$g(x)=1+x+x^2+x^3+\cdots=\frac{1}{1-x}$$ $$7\times g(x)=7+7x+7x^2+7x^3=\frac{7}{1-x}$$ ...
1
vote
2answers
40 views

Definition of Finite Projective Plane clarification

I do not understand part iii. Why can't there be four collinear points? The Fano plane is an example of a $3$-uniform configuration. What about configurations that are $4$-uniform? You must ...
1
vote
2answers
45 views

simple combinatorics - where is my mistake

In the olympic games we want to organize 8 flags on 8 poles, 4 US flags, 2 french flags, 2 german flags. We want to know how many combinations are there where a US flag is adjacent to a french flag. ...
0
votes
1answer
22 views

Stirling number of first kind monotone for a half

Show that every $n>0$, there is some $m(n)$ such that $$s_{n,0}<s_{n,1}<\cdots < s_{n,m(n)}>s_{n,m(n)+1}>\cdots>s_{n,n},$$ where either $m(n)=m(n-1)$ or $m(n)=m(n-1)+1$ and ...
0
votes
0answers
24 views

Explicit form of a generating function.

Let $q \geq p$ be natural numbers both larger than or equal to two. Let $u(z):=z^p+z^{p+1}+...+z^q$ and $p(z)=\frac{z u'(z)}{1-u(z)}$. Since $p(z)$ is rational, one can write (by the theory of ...
0
votes
1answer
32 views

For any positive integer $n$, let$ G_n$ be the graph whose vertices are all binary string of length $n$

For any positive integer $n$, let $G_n$ be the graph whose vertices are all binary string of length $n$ that have precisely two block of 1's, each of which is of length at most 3, and two vertices are ...
0
votes
0answers
17 views

Anti diagonal elements of table forming pascal traingle

A function in $k$ and $n$ leads to the formation of this table. The elements in this table are rows of pascal triangle if we look at the anti diagonals elements of this table. They have also been ...
0
votes
1answer
593 views

Prove that the antichain of $\mathcal P(\{1,2,3,4\})$ of size $6$ is unique

Let $S=\{1,2,3,4\}$. Consider the power set $\mathcal P(S)$ as a poset under the usual subset ordering. Prove that the only antichain of $\mathcal P(S)$ of size $6$ is the antichain of all ...
2
votes
2answers
36 views

COMBINATORY LOGIC: Cards extraction from a deck of 32 cards.

5 cards are extracted simultaneously from a standard deck of 32 cards (8 cards for each of the four suits (hearts, diamonds, spades and clubs): 7,8,9,10, Jack, Queen, King, Ace). How many ...
4
votes
1answer
49 views

How many 4-digit numbers contains number 42

How many 4-digit numbers contains number 42 only once(without leading zero) For example, 4002 - not Ok, 3425 - Ok My answer: Count of 42xx = 10*10=100 Count of x42x = 9*10 = 90 Count of ...
1
vote
2answers
36 views

How many ways are there to order $n$ women and $n$ men in circle

I have the following question : How many ways are there to order $n$ women and $n$ men in circle so there is no man next to man and no woman next to man meaning the order is man,woman,man,woman... ...
0
votes
4answers
50 views

How many ways are there to order in circle $n$ couples so each men sitsin front of his wife

I have the following question : How many ways are there to order in circle $n$ couples so each men sits infront of his wife? I thought of something like that : Lets take wife $n$ and sit her down ...
3
votes
1answer
55 views

Tic Tac Toe: What is the probability that a random player draws against an infallible player?

I have simulated a tournament between an infallible Tic Tac Toe player and one that chooses its moves randomly. Even after 5 million games, the infallible player wins every single game. I know that ...
1
vote
1answer
21 views

Giving coordinates in a projective plane

When we are giving coordinates to the points of the Fano plane, we do so by giving every point a triplet: $(a_1, a_2,a_3)$ from $\mathbb F_2$ so that if three points are collinear then the pointwise ...
1
vote
0answers
54 views

Finding a formula for number of permutations satisfying pattern constraints

I'm trying to find a formula that gives the number of unique permutations of a set of 3 values of n length given a set of constraints. The values: $-1, 0, 1$ Example Set: $[0, -1, 1, 1, 1, 1]$ the ...
17
votes
5answers
881 views

A strange combinatorial identity [duplicate]

In reading about A polarization identity for multilinear maps by Erik G F Thomas, I am led to prove the following combinatorial identity, which I cannot find anywhere, nor do I have any idea how to ...
-1
votes
1answer
18 views

number of combinations of numbers 1 to 12

I have 12 couples meeting for dinner each week in groups of 4. How many times can they meet without any couple meeting twice? Is there a table I could use to figure all the ...
0
votes
1answer
49 views

Does any one know a closed form for $1+\sum \limits_{s=1}^{d} \frac{x^s}{1-x^s}$?

Does any one know a closed form for $1+\sum \limits_{s=1}^{d} \frac{x^s}{1-x^s}$? To me, it is the generating function $f(x)=\sum f_n x^n$, where $f_n$ counts the number of composition of $n$ that ...
14
votes
1answer
405 views

How many $n$-element subsets $A$ of $\{1,2,3,\cdots,2n\}$ with specified sum are there?

Question: Let $ n$ be an postive integer number.and let $A=\{x_{1},x_{2},\cdots,x_{n}\}$, How many $ n$-element subsets $ A$ of $ \{1,2,\dots,2n\}$ are there,such ...
2
votes
0answers
29 views

Can anyone give an example of a set of numbers with arithmetic density that doesn't converge to a limit?

Question in the title. All of the examples I can think of (congruence classes, primes, etc.) converge as n goes to infinity.
3
votes
4answers
76 views

Let $A= \{1,2,3,4,5,6,7,8,9,0,20,30,40,50\}$. 1. How many subsets of size 2 are there? 2.How many subsets are there altogether?

Let $A= \{1,2,3,4,5,6,7,8,9,0,20,30,40,50\}$. 1. How many subsets of size $2$ are there? 2.How many subsets are there altogether? Answer: 1) I think there are $7$ subsets of size two are ...
1
vote
1answer
78 views

Number of k-products of disjoint cycles in the symmetric group S(n)

Suppose that $S(n)$ denotes the group of all permutations of the set $\{1,2,...,n\}$ with the usual composition operation. Is there any formula or expression for $n(k)$, where $n(k)$ denotes the ...
0
votes
1answer
167 views

Number of trailing zeros at other bases

Q. $85!$ ends with exactly $20$ trailing zeros. When $85!$ is converted to base $N$, $N$ being any natural number, it so happens that it has the same number of zeros at the end. What could be the ...
3
votes
2answers
78 views

how many distinct values does it have?

I solved this problem by manually adding parentheses and counting them, and got correct answer of 32. Is there a simple to find the answer? Thanks. The value of the expression $1÷2÷3÷5÷7÷11÷13$ ...
3
votes
3answers
468 views

How many sets of two factors of 360 are coprime to each other?

My attempt: $360=2^3\cdot3^2\cdot5^1$ Number of sets of two factor coprime sets for $2^3$ and $3^2$ only $=12+6=18$ With that if we add the effect of $ 5^1$, number of sets $=18+2\cdot 18-1=53$. ...
-2
votes
1answer
21 views

Hints for Solving Elementary Combination problem of Doughnuts. [closed]

There are eight varieties of Doughnuts, if a box contains $1$ dozen doughnuts how many different option are there for a box of doughnuts ?
0
votes
0answers
16 views

Approximating the coefficients of $\prod_{i=1}^{N}\frac{1}{1-\frac{1}{2}q^i}$ for large $N$

I have $$\frac{1}{2^{N}}\prod_{i=1}^{N}\frac{1}{1-\frac{1}{2}q^i}$$ the reciprocal of the q-Pochhammer symbol $(\frac{1}{2},q)_{N+1}$ (multiplied by a power of $1/2$). Its Maclaurin series for ...
4
votes
4answers
129 views

Find a generating function for the number of strings

The string $AAABBAAABB$ is a string of ten letters, each of which is $A$ or $B$, that does include the consecutive letters $ABBA$. Determine, with justification, the total number of strings of ten ...
2
votes
0answers
17 views

Is a simplex with permuted vertices $\pm$homologous to the original?

Take a singular $n$-simplex $\sigma: \Delta^n \to X$, where $\Delta^n\subset \mathbb{R}^{n+1}$ is the convex hull of the standard basis, with the obvious vertex ordering. Then one can obtain $(n+1)!$ ...
2
votes
2answers
72 views

Odd binomial sum equality has only trivial solution?

Suppose $$\sum_{k\ {\rm odd}}^n {n \choose k} 2^{(k-1)/2} = \sum_{k\ {\rm odd}}^m {m \choose k} 2^{(k-1)/2} 3^{(m-k)/2}.$$ Does $m=n=1$? Clearly $m \leq n$, and for every $n$ there is at most one ...
2
votes
2answers
24 views

Construction of a finite projective plane of order $p$, for any prime $p$

I have this construction of a finite projective plane (FPP) of prime order $p$, but I am not sure what's going on. We have already proved that FPPs of order $q$ have $q^2+q+1$ lines and points (if ...