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
0answers
37 views

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

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 ...
0
votes
1answer
51 views

What are some efficient ways to go about a problem where you cannot exceed the other by 2?

I need an efficient way to go about this problem, for practice for my problem solving test. This is not a part of the actual test. This is the type of question that I am struggling with There are two ...
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 ...
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 ...
7
votes
1answer
78 views

Repeatedly taking mean values of non-empty subsets of a set: $2,\,3,\,5,\,15,\,875,\,…$

Consider the following iterative process. We start with a 2-element set $S_0=\{0,1\}$. At $n^{\text{th}}$ step $(n\ge1)$ we take all non-empty subsets of $S_{n-1}$, then for each subset compute the ...
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}$$ ...
-4
votes
1answer
55 views

The total number of subsets of a set of size 1001 is odd. [on hold]

Given the statement "The total number of subsets of a set of size 1001 is odd." determine its truthfulness. I believe the answer is that the statement is false. Could someone please provide a ...
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 ...
0
votes
2answers
34 views

How many ways are there to select $15$ cookies if at most $2$ can be sugar cookies? [on hold]

A cookie store sells 6 varieties of cookies. It has a large supply of each kind. How many ways are there to select $15$ cookies if at most $2$ can be sugar cookies? For my answer, I put $6 \cdot ...
1
vote
1answer
25 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
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) ...
4
votes
2answers
36 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
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
0answers
22 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
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
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 ...
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 ...
4
votes
1answer
34 views
+100

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 ...
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 ...
1
vote
3answers
22 views

How many duplicates are eliminated via sorting?

This is a problem I've encountered when using a set as a key for a lookup table. Say I have to map a set of letters (lets say, $4$) to some (unspecified) result with a dictionary/array/etc. For ...
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.
0
votes
1answer
48 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 ...
1
vote
0answers
53 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 ...
-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 ...
3
votes
4answers
71 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
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 ...
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$ ...
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
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 ...
1
vote
0answers
58 views

Lower bound related to Goldbach conjecture

I am curious to know if a lower bound on the number of ways (call this $\beta$ and assume $p_1 + p_2$ distinct from $p_2 + p_1$) in which two primes $p_1, p_2$ that add up to a given even integer $n$, ...
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
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 ...
-2
votes
1answer
21 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
24 views

Understanding Theorem on Combinatorics.

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

How large can a set of pairwise disjoint 2-(7,3,1) designs (Fano planes) be?

As wikipedia defines well, the Fano plane is a small symmetric block design, specifically a 2-(7,3,1)-design. The points of the design are the points of the plane, and the blocks of the design are the ...
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 ...
0
votes
0answers
49 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
35 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.
17
votes
5answers
860 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
1answer
35 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 ...
6
votes
1answer
66 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 \!\!\!\! ...
1
vote
1answer
61 views

How many partial derivatives does a multivariate polynomial have?

My motivation for this question is from the following toy example; define the (nondeterministic) finite state machine generated by the polynomial $f(x_0 , ... , x_n) \in \mathbb{Z} [x_0 , x_1 , ... , ...
-4
votes
0answers
17 views

Number of Non Decreasing Sequence. [closed]

I have to find the number of non decreasing sequence (A,B,C,D) such that ...
0
votes
1answer
25 views

probability for two people to arrange something in the same order

What is the probability that two people independently arrange for instance a sequence of the $10$ elements: $0,1,2,3,4,5,6,7,8,9$, in the same order? I'm not sure how I should go about this problem, ...
5
votes
1answer
63 views

Combinatorial proof of a certain alternating sum of binomial coefficients

The following identity appeared as a question earlier today $$\displaystyle\sum\limits_{k=0}^n (-1)^k\binom{m+1}{k}\binom{m+n-k}{n-k} = \begin{cases} 1\ \text{if}\ n=0 \\ 0\ \text{if}\ n>0 ...
1
vote
3answers
42 views

Seating arrangements of 7 boys and 5 girls in a row.

In how many ways can these boys and girls be arranged in a row if between two particular boys A and B there are no boys but exactly 3 girls?
157
votes
16answers
28k views

Do men or women have more brothers?

Do men or women have more brothers? I think women have more as no man can be his own brother. But how one can prove it rigorously? I am going to suggest some reasonable background assumptions: ...
-1
votes
0answers
17 views

A SDR extension problem [closed]

enter image description here I think we should use induction. for subset I when $|I|=1$ then we have for any $i\in \{1,\dots,n\}$ $|A_i|\leq 2$. Then for any $A_i$ we have $2$ SDR. then we suppose ...
4
votes
0answers
46 views

Find the number of 4 digit numbers of the form $abcd$ such that $ab+cd$ is even

Let $n$ denote the number of 4 digit numbers of the form $abcd$ such that $ab+cd$ is even. Find the last digit of $n$. There are two cases. $ab,cd$ is odd. Which means $a,b,c,d \in \text{odd}$. ...