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)

2
votes
1answer
26 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
27 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
20 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 ...
4
votes
1answer
31 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
0answers
18 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
8 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 ...
-3
votes
0answers
43 views

Prove that random graph G(n, ln^2⁡n/n^2 ) obeys 0-1 law? [on hold]

I tried to solve but I couldn't understand how to solve it. Let G be a graph in G(n, p) (Erdős–Rényi model) 0-1 law means Fagin's 0-1 law for first-order properties of random graphs , where ...
0
votes
1answer
29 views

What are some effective ways to go about this type of problem?

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 ...
-3
votes
0answers
11 views

Prove that P( in G(n,p) the number of tree components on 11 vertics = 0) tends to 1

Let G be a graph in G(n, p) (Erdős–Rényi model) I want to prove that the P(G(n, p) where number of tree components on 11 vertices = 0 ) converges to 1 where p ≥ ln n / 10 n
4
votes
1answer
29 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
18 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}$$ ...
2
votes
0answers
13 views

Convergences in probability and distribution for the number of trees in random graph $G(n,p)$

As we know the binomial random graph $G(n, p)$ is the disjoint union of trees for $p\sim o(1)$ and by the results from Erdos-Renyi's article on the evolution of random graphs; we know that the ...
-4
votes
1answer
36 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 ...
1
vote
2answers
36 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
2answers
115 views

How many different Fano planes we can build with {1, 2, …, 7} numbers?

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 ...
1
vote
0answers
17 views

Zero-one law in binomial random graph model $G(n,p)$

Consider the binomial random graph model $G(n,p)$ with $0<p<1$. We say that $G(n,p)$ satisfies the Zero-One law if for every first order property $Q$ one has $\lim\limits_{n \rightarrow \infty} ...
103
votes
15answers
17k 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: ...
3
votes
1answer
25 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
40 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
18 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
18 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
30 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
15 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
591 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
33 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
48 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
35 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
46 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
11 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
19 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
43 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
830 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
58 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
vote
3answers
19 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 ...
-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 ...
1
vote
1answer
41 views

How many partial derivatives does a multivariate polynomial have?

For instance the polynomial $f(x,y) = xy$ in $\mathbb{Z}[x,y]$ has $xy$ (we'll say the zeroth partial counts), $x,y, 1,$ and $0$ as partial derivatives, so the answer in this case is five. I think ...
12
votes
2answers
344 views
+100

Dividing books between two couples

Two couples of boys and girls, $(b_1,g_1)$ and $(b_2,g_2)$, are dividing a pile of books. Every book will go to one of the couples, and they'll read it together. Each person has a (nonnegative) value ...
0
votes
1answer
46 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
404 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
27 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
63 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
17 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
70 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
463 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 ...