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)

3
votes
1answer
38 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
23 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
21 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
24 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
25 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
37 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 ...
3
votes
1answer
29 views

prove simple sum, combinatorics

I want to prove that $\sum_{i = 1}^{n} \binom{n}{i}\binom{n}{i-1} = \binom{2n}{n-1}$ On the right hand side we simply have the coefficient of $x^{n-1}$ of the term $(1+x)^{2n}$ But on the other ...
1
vote
2answers
43 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
21 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
16 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
592 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
35 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
54 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 ...
3
votes
0answers
15 views

Maximum value of the smallest number of operations to obtain configuration from original configuration

Let $n$ be a positive integer. There are $n(n+1)/2$ marks, each with a black side and a white side, arranged into an equilateral triangle, with the biggest row containing $n$ marks. Initially, each ...
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
52 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
852 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 ...
0
votes
0answers
59 views

Sequence of integers in given range that sums up to given value

I'm trying to find out, if there is a way to find the total number of possible combinations of integers $x_i \in [l,u] \cap \mathbb{Z}$ for all $i = 1,\ldots,n$ that sum up to $A$. Generally, ...
-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
47 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
28 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
67 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 ...
0
votes
0answers
25 views
+50

What is the number of interior faces adjacent to an interior vertex in a triangulation in $\mathbb{R}^3$?

Let $\Omega$ be a polygonal domain in $\mathbb{R}^3$. Assume $\Omega$ is partitioned into tetrahedra using the most common admissible triangulation, that is, roughly speaking, two adjacent tetrahedra ...
1
vote
1answer
77 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
166 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
75 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
464 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
2answers
19 views

Hints for Solving Elementary Combination problem of Doughnuts. [on hold]

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
127 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
16 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
71 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 ...
0
votes
0answers
24 views

Understanding Theorem on Combinatorics.

What following Theorem wants to convey (how there can be infinite repetitions), pls give some examples to explain.
0
votes
0answers
48 views

Number of valid parenthesis

I have to find out the number of valid parenthesis.Parenthesis are of two type [] ,(). How many ways are there to construct a valid sequence using ...
0
votes
1answer
34 views

Calculating the coefficient of a generating function

Calculate the coefficient of $x^{10}$ in $$\frac{1+x^3}{1-2x+x^3-x^4}$$ I am unsure how to even start and would appreciate a hint? I haven't dealt with problems like this (complicated) before.
0
votes
1answer
34 views

Number of possible subsequences

Given 4 integers - $A,B,C,D$ such that $A \leq B \leq C \leq D$ (i.e they are in non decreasing order). Now we need to find number of possible non decreasing subsequences $(W,X,Y,Z)$ such that $1 ...
0
votes
2answers
591 views

Coupon collector problem for collecting set k times.

Recently I tried to solve a problem that based on coupons collector problem. Let it be sth like this: If a package has one of 50 random baseball cards, how many packages do you need to buy to get a ...
5
votes
2answers
852 views

Is there a memorable solution to Kirkman's School Girl Problem?

Given a solution to Kirkman's School Girl Problem, it is of course easy enough to check that it actually is a solution. But how could you reconstruct it if you lost it? Is there a method or algorithm ...
1
vote
2answers
56 views

Integer solutions to an equation with a constant before x

The question is: How many integer solutions are there to the equation $$x_1 + x_2 + x_3 + x_4 + 3x_5 = 80$$ if $x_i$ is greater than or equal to 0? I understand how to get integer solutions to a ...
6
votes
1answer
65 views

Matrices and prime numbers

Let $ p $ be a prime number and \begin{align} K=\left\{ \begin{pmatrix} a &b \\ c& d \end{pmatrix} \mid a,b,c,d \in \left\{0,1,\ldots,p-1 \right\}, \right. & a+d \equiv 1 \!\!\!\! ...
5
votes
4answers
132 views

Finding the sum $\sum_{j=k}^n (-1)^{j+k}\binom{n}{j}\binom{j}{k}$

I am prepping for my mid semester exam, and came across with the following question: Find the closed form for the sum $\sum_{j=k}^n (-1)^{j+k}\binom{n}{j}\binom{j}{k}$, using the assumption that ...