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
24 views

What is the maximum number of subsets can be formed from n data subsets?

What is the maximum number of subsets can be formed from $n$ data subsets of a fixed set by the operation of intersection, union, and complement? I think the answer is $2^{2^n}$. Because $2^n$ ...
2
votes
0answers
19 views

Alternating sum of subfactorials: Is there a closed form for this: $\displaystyle \sum_{i=0}^{m-2}(-1)^i\left[\frac{(m-i)!}{e}\right]$?

The problem was to find the number of ways in which $n$ objects in circular arrangement can be placed so that each one has a new object in front of it (assuming a particular, initial arrangement). ...
1
vote
2answers
450 views

Find recurrence relation for ternary strings that don't have substrings 00, 01 and last symbol is not 0

I am preparing for my finals for discrete mathematics and I came across this exercise in textbook. Let $s_{n}$ denote all ternary strings of length $n$, such that any string in $s_{n}$ does not ...
3
votes
2answers
58 views

Number of ways to re-arrange INTERNATIONAL with L to the right of E.

How many ways can you re-arrange I N T E R N A T I O N A L such that L is always to the right of E, it does not need to be a specific number of places, so both E L I N T R N A T I O N A ...
0
votes
0answers
11 views

Selecting minimal no. of unit kth dimensional cubes in kth dimensional cube (nxn…xn) so that each remaining is on axis of selected cubes

This comes from a old Russia MO problem, which asks for ($k=3$), among the set of $k$-tuples $(a_1,...,a_k)$, $1\leq a_i\leq n$, what is the minimal number of tuples chosen such that for any remaining ...
7
votes
1answer
287 views

Sum of product with primes

Let $b=e_1e_2,\ldots,e_n$ and $b'=e'_1e'_2,\ldots,e'_n$ be two distinct bit strings of equal length $n$ with same number of occurrences of zeros and ones. The bit string $b$ and $b'$ also must have ...
2
votes
1answer
32 views

polynomial representing a self-orthogonal latin square

I need to show that for $q$, a prime power not equal to 2 or 3, the polynomial $f(x,y) = \lambda x+(1-\lambda)y$ represents a self-orthogonal latin square of order $q$, where $\lambda \in F_{q}$ is ...
14
votes
2answers
359 views

Strehl identity for the sum of cubes of binomial coefficients

In 1993 Strehl showed that $$ \sum_k\binom nk^3=\sum_k\binom nk^2\binom{2k}n. $$ I’m interested in a combinatorial proof. Upd (Jan '14). Maybe the original question was too restrictive — I'm now ...
0
votes
1answer
49 views

Tiling problem : Number of ways a floor can be tiled

Find number of ways a floor n meter length and 11 meter wide can be floored with tiles of 2 cm length and 1 cm wide wide tiles without breaking the tiles (assume n is even) Could you please help in ...
1
vote
2answers
39 views

Derive formula for number of cables in full-mesh network

I am trying to determine how they derived number of cables needed in a full mesh network According to networking books it is $\dfrac{N * (N-1)}{2}$, where N is the number of nodes. I tried drawing ...
3
votes
1answer
32 views

Integer Partitions and distinguishable permutations

I'm not a mathematician but I'm faced with a problem where I can't find an answer, also because I do not know what I shall ask for: I have to deal with partitions of an integer k, only small values, ...
1
vote
1answer
32 views

coefficient of operator for $B_{n,k}^{x^2}(x)$

We start with the following: $$ (x+z)^2 - x^2 = \sum_{n \geq 1} \frac{z^n}{n!} \frac{d^n}{dx^n}[x^2] $$ $$ (x+z)^2 - x^2 = z(2x+z) $$ $$ z^k(2x+z)^k = \sum_{n \geq k} Y^{\Delta}(n,k,x)z^n $$ Where ...
15
votes
2answers
425 views

Show that $ \sum_{r=1}^{n-1}\binom{n-2}{r-1}r^{r-1}(n-r)^{n-r-2}= n^{n-2} $

Show that $$ \sum_{r=1}^{n-1}\binom{n-2}{r-1}r^{r-1}(n-r)^{n-r-2}= n^{n-2} $$ I don't know whether such identity already exists, or has been posted here before. I discovered this identity while ...
-1
votes
0answers
30 views

Number of simple, connected graphs with K edges and N distinctly labelled vertices [closed]

Ok. I'm aware of this question and answer, but it's over my head. I've written a recursive function that I thought would do the job, but it doesn't, apparently. Could someone explain to me why it's ...
2
votes
0answers
8 views

Special class of Brenke Polynomials

I was wondering if there are any particular papers dealing with a particular class of Brenke Polynomials, defined as $$A(t)B(xt)=\sum_{n\ge 0}P_n(x)t^n$$ where $A=B$ or, where $A(t)=C(B(t),t)$ for a ...
1
vote
1answer
67 views

Coefficient of operator and how to do it

This question stems from this $$ \frac{1}{x+z}- \frac{1}{x} = \sum_{k=0}^\infty \frac{z^k}{k!}\frac{d^k}{dx^k}[\frac{1}{x}] $$ Now, i need to find the Bell Polynomial of $\frac{1}{x}$, $$ ...
18
votes
2answers
872 views

Not lifting your pen on the $n\times n$ grid

Does there exist $n$, and $r<2n-2$, such that the $n\times n$ square grid can be connected with an unbroken path of $r$ straight lines? Note: This has essentially already been asked - see this ...
4
votes
1answer
150 views

Why aren't there 21 players in this tournament?

In a tournament each player played exactly one game against each of the other players. In each game the winner was awarded 1 point, the loser got 0 points, and each of the two players earned ...
3
votes
2answers
80 views

Probability with changing number of marbles

Given a bag containing 20 marbles of 5 different colors in this configuration: 8x Blue 6x Red 3x Green 2x White 1x Black How would you determine the probability of picking a marble of a specific ...
3
votes
1answer
63 views

Another Evaluation of the Ramsey number $\mathcal{R}(3,3,3)$

The problem Show that $\mathcal{R}(3,3,3)=17$ The story behind the problem and some notation It was first proven by Greenwood and Gleason in 1955 in their paper Combinatorial relations and ...
0
votes
2answers
26 views

Student card handing Inclusion–exclusion principle

I got the following question and would very much appreciate any help with understanding it solution. "5 Student cards are handed to 5 students so that each student gets 1 student card, what is the ...
0
votes
2answers
40 views

Number of permutation with condition

Assume we have a group consisting of both women and men. (In my example it is 67 women and 43 men but that is not important.) The women are indistinguishable and the men are also indistinguishable. ...
1
vote
1answer
12 views

How many Schedules possible with given set of Transactions? Given that total ordering of operations in a transactions is there.

Given that : There are $m$ transactions = $\{T_1, T_2, \dots, T_m\}$ and for each transaction $T_i$ there are $n_i$ operations in it. It is required that the relative ordering of operations within ...
2
votes
2answers
55 views

Probability Modem is Defective

A store has 80 modems in its inventory, 30 coming from Source A and the remainder from Source B. Of the modems from Source A, 20% are defective. Of the modems from Source B, 8% are defective. ...
-1
votes
1answer
29 views

Functions from $\{w,x,y,z\}$ to $\{a,b,c\}$

I'm having some problems understanding how functions and Big-O notation works... I've checked a couple of other threads here but still unsure Let's say I have $A = \{w, x, y, z\}$ and $B = \{a, b, ...
0
votes
1answer
37 views

How do I prove the formula for multichoose?

In combinatorics, there is a formula "$n$ multichoose $k$", which is the way of making a multiset having $k$ elements choosing out of $n$ options. "$n$ multichoose $k$" is the same as "$(n+k-1)$ ...
-2
votes
0answers
55 views

How many increasing functions $f:\{1,\ldots,n\} \to \{1,2,\ldots,n\}$ are there such that $f(i) \ge i , \forall i=1(1)n$ , where $n \in \mathbb N$?

Let $n\in \mathbb N , n \ge 3$ . How many increasing functions $f:\{1,,\ldots,n\} \to \{1,2,\ldots,n\}$ (i.e. $f(i) \ge f(j) , \forall i=1(1)n$ ) are there such that $f(i) \ge i , \forall i=1(1)n$ ?
2
votes
1answer
24 views

combinatorics problem: find all possible ordered permutations in a tuple

I have a tuple that looks like this: $(1,2,3,4)$ I want to generate all possible nested tuples that can be made from the original tuple which maintain the original order of the array. For the ...
0
votes
3answers
39 views

Girls and boys ordering combinatorics

I have the following combinatorics question but I don't know how to approach it: "10 girls and 4 boys are about to be photographed in a row, how many ordering options are there if between each 2 ...
2
votes
1answer
133 views

Lengths of the shortest “simple” equation, that use only the number '1', equal to a given natural numbers.

Is there a formula, for determining the length of the shortest formula, that uses only the number '1', parenthesis, and the hyperoperations $\{\{+, - \}, \{\times, / \}, \{\text{^}, \log_N,\text{nth ...
1
vote
1answer
27 views

Lower bound for the size of a maximal matching in a general graph

Let $G=(V,E)$ be a graph, let $M\subseteq E(G)$ be a maximal matching, and let $M^\star\subseteq E(G)$ be a maximum matching. Prove that $|M|\ge |M^\star|/2$. Any hints on how to prove this?
1
vote
2answers
30 views

Simple counting question- numbers in sequences.

I'm taking a counting/probability course. Got this one question that I originally thought was simple, but my solution turned out to be wrong. "How many $6$-digit sequences have a digit that appears ...
0
votes
0answers
17 views

Enumeration of skew Ferrers diagrams revisited.

In M. P. Delest, J. M. Fedou, "Enumeration of skew Ferrers diagrams", Discrete Mathematics. vol.112, no.1-3, pp.65-79, (1993) http://dx.doi.org/10.1016/0012-365X(93)90224-H a generating function is ...
1
vote
1answer
40 views

Expectation value of number of trials to select all tokens with replacement

(I suppose this is analogous to the coupon collector's problem) I have an infinitely large bag containing tokens marked equiprobably with a number from 1 to $k$ i.e. the probability of selecting any ...
1
vote
2answers
26 views

Expectation value of number of drawings of increasing sequences of labelled balls from an urn.

An urn contains $n$ balls, labelled from $1$ to $n$. A sequence of drawings with re-insertion is made, until the drawn ball is labelled with a number which is less than or equal to the number of ...
0
votes
1answer
27 views

Balls and Boxes Generalization

Recently, I saw a problem here on MSE: $$$$"Put 9 pigs in 4 pens such that there are an odd number of pigs in each pen." Individual cases or solutions to the problem are quite easy. But how would we ...
0
votes
1answer
24 views

number of binary strings with equal number of 0's and 1's

I am trying to count the number $S$ of binary strings with equal number of 0's and 1's. Since this boils down to picking $n$ out of $2n$ places where 0's can fall into, my ansatz is $$ S = ...
0
votes
1answer
56 views

Some proofs regarding Stirling numbers

I would like you to help me to prove two proofs correlated with Stirling numbers (the first one includes Stirling numbers of the second kind and the second one I guess Stirling numbers of the second ...
0
votes
0answers
29 views

Looking to get a handle on SSCG(3) (which is much, much larger than TREE(3))

TREE numbers grow rapidly: TREE(1) = 1, TREE(2) = 3, and a lower bound for TREE(3) is A(A(...A(1)...)), where the number of As is A(187196) and A(n) is a version of Ackerman's function. That's ...
0
votes
1answer
56 views

From a bag containing $10$ pairs of socks, how many must a person pull out to ensure that they get at least $2$ matching pairs of socks? [closed]

There are $10$ pairs of socks in bag. What is the minimum number of socks that a person should pull out from the bag to ensure that they get at least $2$ matching pairs of socks.
5
votes
0answers
225 views

Formula for composition of formal power series with binomial coefficient

Let $f=\sum\limits_{n\geq 0}{f_n x^n}$ and $g=\sum\limits_{n\geq 1}{g_n x^n}$ be formal power series. The $x^n$ coefficient of $f(g)$ is $$ \sum\limits_{\mathbb{i} \in \mathcal{C}_{n}} {f_k ...
0
votes
1answer
30 views

How many sequences of lenght 2n, made of n “+1”s and n “-1”s and such that every partial summation of the first k terms is nonnegative, are there?

What's the number of sequences $$(u_{1},...,u_{2n})$$ with $u_{i}=+1,-1$, such that: $$\sum_{j=1}^{2n} u_{j}=0\quad\hbox{and}\quad \sum_{j=1}^{k} u_{j}\geq 0$$ I realized that $u_{1}=+1$ and ...
7
votes
0answers
57 views

Dominating a Four Dimensional Chessboard with Rooks

There is a family of chess problems where you try to dominate a board with as few copies of a given piece as possible. The chessboard is dominated if every square either contains a piece, or is ...
6
votes
2answers
8k views

Number of bit strings with 3 consecutive zeros or 4 consecutive 1s

I am trying to count the number of bit-strings of length 8 with 3 consecutive zeros or 4 consecutive ones. I was able to calculate it, but I am overcounting. The correct answer is $147$, I got $148$. ...
2
votes
2answers
67 views

100 prisoners 100 boxes problem

I have some issues with a problem I found on this page: http://www.mast.queensu.ca/~peter/inprocess/prisoners.pdf The problem goes as follows: "A group of 100 condemned prisoners are offered the ...
1
vote
1answer
129 views

How to prove it's possible to place $8$ non-attacking rooks on a chessboard with $7$ cells cut out?

From the 8 × 8 chessboard 7 cells were cut out. Prove that you can put 8 rooks to this board so that none of them can capture another rook.
6
votes
1answer
65 views

Poker Combinations: How many ways can you get 4 of the same suit in a hand of 5 cards?

The homework question is: in how many ways can we get exactly 4 cards of the same suit in a hand of 5 cards? (Order does not matter.) Here is what I have: we need to pick two different suits, decide ...
2
votes
2answers
26 views

Is this equivalent to Szemerédi's theorem?

I know that Szemerédi's theorem states that any set of integers with positive natural density contains arbitrary long arithmetic progressions. However, does this imply that such a set contains an ...
1
vote
1answer
47 views

What is the combinatorial proof for the formula of S(n,k) - Stirling numbers of the second kind?

What is the combinatorial proof for the formula of Stirling numbers of the second kind ? i.e. S(n,k) where n is the number of objects and k is the number of parts $${n\brace ...
2
votes
1answer
32 views

Let $S = \{1,2,3,…,1992\}$ find the number of subsets $\{a,b,c\}$ such that $3\mid(a+b+c)$.

Let $S = \{1,2,3,...,1992\}$ find the number of subsets $\{a,b,c\}$ such that $3\mid(a+b+c)$. I managed to solve the same problem but with 2-elements sets in the following way: Make the ...